package q994;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * 994. 腐烂的橘子
 */
public class Solution {

    int minDay = 0;

    public int orangesRotting(int[][] grid) {
        List<Integer> list = new LinkedList<>();
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == 2) {
                    list.add(i);
                    list.add(j);
                }
            }
        }

        dfs(grid, list, 3);

        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == 1) {
                    return -1;
                }

                if (grid[i][j] >= 2) {
                    minDay = Math.max(minDay, grid[i][j] - 2);
                }
            }
        }
        return minDay;
    }

    public void dfs(int[][] grid, List<Integer> list, Integer day) {
        if (list.isEmpty()) return;
        LinkedList<Integer> list1 = new LinkedList<>();
        for (int i = 0; i < list.size(); i += 2) {
            int row = list.get(i);
            int col = list.get(i + 1);

            if (isFreshOrg(grid, row - 1, col)) {
                grid[row - 1][col] = day;
                list1.add(row - 1);
                list1.add(col);
            }
            if (isFreshOrg(grid, row + 1, col)) {
                grid[row + 1][col] = day;
                list1.add(row + 1);
                list1.add(col);
            }
            if (isFreshOrg(grid, row, col - 1)) {
                grid[row][col - 1] = day;
                list1.add(row);
                list1.add(col - 1);
            }
            if (isFreshOrg(grid, row, col + 1)) {
                grid[row][col + 1] = day;
                list1.add(row);
                list1.add(col + 1);
            }
        }
        dfs(grid, list1, day + 1);
    }

    // 是否是新鲜的橘子
    public boolean isFreshOrg(int[][] grid, int row, int col) {
        return row >= 0 && col >= 0 && row <= grid.length - 1 && col <= grid[0].length - 1 && grid[row][col] == 1;
    }

    public static void main(String[] args) {
        int[][] grid = new int[][]{{2,1,1},{1,1,0},{0,1,1}};
        Solution solution = new Solution();
        System.out.println(solution.orangesRotting(grid));
    }
}
